/**
 * Copyright (C) 2008+ Spark Zheng
 *
 *
 * @file	src/misc.c
 * @brief       miscellaneous functions
 *
 * @module      dlib
 * @see		dlib
 * @history     
 *		version 0.1.0 spark add max/min str_similiar
 */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

#include "misc.h"

/** @deprecated, just use dlib_nmax instead */
inline int max_n(int *array, int *n)
{
	int ret;
	int i;
	int count = *n;

	if (array == NULL || *n == 0)
		return 0;

	ret = array[0];
	*n = 0;
	for (i = 1; i < count; i++) {
		if (ret < array[i]) {
			ret = array[i];
			*n = i;
		}
	}
	return ret;
}

/** @deprecated, just use dlib_nmin instead */
inline int min_n(int *array, int *n)
{
	int ret;
	int i;
	int count = *n;

	if (array == NULL || *n == 0)
		return 0;

	ret = array[0];
	*n = 0;
	for (i = 1; i < count; i++) {
		if (ret > array[i]) {
			ret = array[i];
			*n = i;
		}
	}
	return ret;
}

/** calculate GCD/LCM */
uint32_t gcd(uint32_t one, uint32_t two)
{
	if (one < two)
		swap(&one, &two, sizeof (uint32_t));
	if (two == 0)
		return one;
	else
		return gcd(two, one % two);
}

uint32_t gcd_n(uint32_t *array, uint32_t len)
{
	if (array == NULL || len == 0)
		return 0;
	if (len == 1)
		return *array;
	return gcd(array[len - 1], gcd_n(array, len - 1));
}

uint32_t lcm(uint32_t one, uint32_t two)
{
	return one * two / gcd(one, two);
}

uint32_t lcm_n(uint32_t *array, uint32_t len)
{
	if (array == NULL || len == 0)
		return 0;
	if (len == 1)
		return *array;
	return lcm(array[len - 1], lcm_n(array, len - 1));
}

/** roundrobin: need remember current weight for rr_scheduler on weight mode */
uint32_t rr_scheduler(uint32_t *weight, uint32_t len, uint32_t prev, int *cw)
{
	uint32_t ret = prev;
	int temp;

	/** no weight array, just round-robin */
	if (weight == NULL) {
		ret = (prev + 1) % len;
		return ret;
	} else {/** weighted round-robin */
		while (1) {
			if (ret == 0) {
				*cw = *cw - gcd_n(weight, len);
				if (*cw <= 0) {
					temp = len;
					*cw = dlib_nmax((int *)weight, &temp);
					if (*cw == 0)
						return 0;
				}
			}
			ret = (ret + 1) % len;

			if (weight[ret] >= *(uint32_t *)cw)
				return ret;
		}/* end while */
	}/* end if */
}

/**
 * ssm_dp, Sub-Sequence-Match:
 * all diff sub-sequences of A exactly match B
 */ 
int32_t ssm_dp(const char *a, size_t len_a, const char *b, size_t len_b)
{
	size_t i, j = 0;

	if (a == NULL || len_a == 0 || b == NULL || len_b == 0)
		return -1;

	int c[len_a][len_b];

	for (i = 1; i < len_b; i++) {
		c[0][i] = 0;
	}
	for (i = j = 0; i < len_a; i++) {
		if (a[i] == b[0]) j++; 
		c[i][0] = j; 
	}

	for (i = 1; i < len_a; i++) {
		for (j = 1; j < len_b; j++) {
			if (i >= j) {
				if (a[i] == b[j]) {
					c[i][j] = c[i-1][j-1] + c[i-1][j];
				} else {
					c[i][j] = c[i-1][j]; 
				}
			} else {
				c[i][j] = 0; 
			}
		}
	}

	return c[len_a-1][len_b-1]; 
}

/**
 * acs_dp, All-Common-Subquence 
 * all diff sub-sequences of A match a sub-sequences of B
 */
int32_t acs_dp(const char *a, size_t len_a, const char *b, size_t len_b)
{
	size_t i, j;
	if (a == NULL || len_a == 0 || b == NULL || len_b == 0)
		return -1;
	int c[len_a][len_b];
	for (i = j = 0; i < len_a; i++) {
		if (a[i] == b[0]) j++;
		c[i][0] = j; 
	}
	for (i = j = 0; i < len_b; i++) {
		if (a[0] == b[i]) j++;
		c[0][i] = j; 
	}

	for (i = 1; i < len_a; i++) {
		for (j = 1; j < len_b; j++) {
			if (a[i] == b[j]) {
				c[i][j] = c[i-1][j] + c[i][j-1] + c[i-1][j-1]; 
			} else {
				c[i][j] = c[i-1][j] + c[i][j-1] - c[i-1][j-1];
			}
		}
	}

	return c[len_a-1][len_b-1];
}


/**
 * lcs_dp, Longest-Common-Subquence 
 * A & B longest common subquence
 */
int32_t lcs_dp(const char *a, size_t len_a, const char *b, size_t len_b,
	      char *res, size_t *len_r)
{
	size_t i, j, k;
	if (a == NULL || len_a == 0 || b == NULL || len_b == 0)
		return -1;
	int c[len_a+1][len_b+1];

	for (i = 1; i <= len_a; i++) {
		c[i][0] = 0;
	}
	for (i = 0; i <= len_b; i++) {
		c[0][i] = 0;
	}
	
	for (i = 1; i <= len_a; i++) {
		for (j = 1; j <= len_b; j++) {
			if (a[i-1] == b[j-1]) {
				c[i][j] = c[i-1][j-1] + 1;
			} else if (c[i-1][j] >= c[i][j-1]) {
				c[i][j] = c[i-1][j];
			} else {
				c[i][j] = c[i][j-1];
			}
		}
	}

	if (res != NULL && len_r != NULL) {
		k = *len_r = c[len_a][len_b];
		i = len_a;
		j = len_b;
		while (i != 0 &&  j != 0) {
			if (c[i][j] == c[i-1][j-1] + 1) {
				k -= 1;
				*(res+k) = a[i-1];
				i -= 1;
				j -= 1;
			} else if (c[i-1][j] >= c[i][j-1]) {
				i -= 1; 
			} else {
				j -= 1; 
			}
		}
	}

	return c[len_a][len_b];
}

/**
 * lis_dp, Longest-increasing-Subquence 
 * A longest increasing subquence
 * O(n^2) not O(nlgn)
 */
int32_t lis_dp(const char *a, size_t len_a, char *res, size_t *len_r)
{
	size_t i, j;
	int32_t ret;
	if (a == NULL || len_a == 0)
		return -1;
	int b[len_a];
	int c[len_a];

	b[0] = 1;
	c[0] = -1;
	for (i = 0; i < len_a; i++) {
		b[i] = 1;
		c[i] = -1;
		for (j = 0; j < i; j++) {
			if (a[i] >= a[j] && b[j] + 1 > b[i]) {
				b[i] = b[j] + 1;
				c[i] = j;
			} 
		}
	}
	for (ret = i = j = 0; i < len_a; i++) {
		if (ret < b[i]) {
			ret = b[i];
			j = i;
		}
	}

	if (res != NULL && len_r != NULL) {
		*len_r = ret;
		for (i = ret; i > 0; i--) {
			*(res + i - 1) = a[j];
			j = c[j];
		}
	}
	return ret;
}


/**
 * edit-distance, levenshtein-distance 
 * the distance between two words 
 * cost array for LD:
 * 1. copy
 * 2. replace
 * 3. delete
 * 4. insert
 * 5. exchange(a[i] <-> a[i+1])
 */
static uint32_t _dlib_ld_weight = 2;
static uint32_t _dlib_ld_costs[5] = {
	0, /** c, copy cost (c <= d) */
	3, /** r, replace cost (r <= 2d)*/
	2, /** d, delete/insert cost */
	2, /** i, insert/delete cost */
	3, /** e, exchange cost (e <= 2r <= 4d) */
};
int32_t levenshtein(const char *a, size_t len_a, const char *b, size_t len_b, char *res)
{
	size_t i, j;
	int k, count;
	if (a == NULL || len_a == 0 || b == NULL || len_b == 0)
		return -1;

	int c[len_a+1][len_b+1];
	int d[len_a][len_b];

	/* init c-array */
	for (i = 0; i <= len_a; i++) {
		c[i][0] = i * _dlib_ld_costs[2];
	}
	for (i = 0; i <= len_b; i++) {
		c[0][i] = i * _dlib_ld_costs[3];
	}

	for (i = 1; i <= len_a; i++) {
		for (j = 1; j <= len_b; j++) {
			if (a[i-1] == b[j-1]) {
				k = 3;
				c[i][j] = dlib_nmin(&k, c[i-1][j] + _dlib_ld_costs[2],
					c[i][j-1] + _dlib_ld_costs[3],
					c[i-1][j-1] + _dlib_ld_costs[0]);
				if (k == 0) {
					d[i-1][j-1] = 'd';
				} else if (k == 1) {
					d[i-1][j-1] = 'i';
				} else {
					d[i-1][j-1] = 'c';
				}
			} else if (i > 1 && j > 1 && a[i-1] == b[j-2] &&
				a[i-2] == b[j-1]) {
				k = 4;
				c[i][j] = dlib_nmin(&k, c[i-1][j] + _dlib_ld_costs[2],
					c[i][j-1] + _dlib_ld_costs[3],
					c[i-1][j-1] + _dlib_ld_costs[1],
					c[i-2][j-2] + _dlib_ld_costs[4]);
				if (k == 0) {
					d[i-1][j-1] = 'd';
				} else if (k == 1) {
					d[i-1][j-1] = 'i';
				} else if (k == 2) {
					d[i-1][j-1] = 'r';
				} else {
					d[i-1][j-1] = 'e';
				}
			} else {
				k = 3;
				c[i][j] = dlib_nmin(&k, c[i-1][j] + _dlib_ld_costs[2],
						c[i][j-1] + _dlib_ld_costs[3],
						c[i-1][j-1] + _dlib_ld_costs[1]);
				if (k == 0) {
					d[i-1][j-1] = 'd';
				} else if (k == 1) {
					d[i-1][j-1] = 'i';
				} else {
					d[i-1][j-1] = 'r';
				}
			}
		}
	}

	if (res != NULL) {
		count = dlib_max(len_a, len_b);
		i = len_a - 1;
		j = len_b - 1;
		*(res+count) = 0;
		for (k = count; k >= 1; ) {
			*(res+k---1) = d[i][j];
			if (d[i][j] == 'c' || d[i][j] == 'r') {
				i = i - 1;
				j = j - 1;
			} else if (d[i][j] == 'd') {
				i = i - 1;
			} else if (d[i][j] == 'i') {
				j = j - 1;
			} else if (d[i][j] == 'e') {
				*(res+k---1) = d[i][j];
				i = i - 2;
				j = j - 2;
			}
		}
	}

	return c[len_a][len_b];
}

/**
 * str_similar_lcs
 * calculate similarity of two strings use LCS
 */
float str_similar_lcs(const char *str_a, size_t len_a, const char *str_b, size_t len_b)
{
	int len_lcs = lcs_dp(str_a, len_a, str_b, len_b, NULL, NULL); 
	if (len_lcs < 0)
		return -1.0;
	else
		return ((float)len_lcs / len_a) * ((float) len_lcs / len_b);
}

/**
 * str_similar_ld
 * calculate similarity of two strings use LD
 */
float str_similar_ld(const char *str_a, size_t len_a, const char *str_b, size_t len_b)
{
	int fact = _dlib_ld_weight;
	int len_ld = levenshtein(str_a, len_a, str_b, len_b, NULL); 
	if (len_ld < 0)
		return -1.0;
	else
		/* care for static weight array, need to adjust fact */
		return (1 - (float)len_ld / (dlib_max(len_a, len_b) * fact));
}
